package my380;

import java.util.*;

/**
 * 实现RandomizedSet 类：
 *
 * RandomizedSet() 初始化 RandomizedSet 对象
 * bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
 * bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
 * int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
 * 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
 */
public class SuanFa380 {
    /**
     * 根据题目需要空间复杂度为O（1）
     * 首先根据随机数查找到现有集合的话，使用数组即可办到，但是通过集合实现时间复杂度为O（1）的操作显然是不行的。
     * 那我们怎么解决这个问题呢？当想到添加和删除数据需要的是O（1）时，我们很容易就会想到使用哈希表！
     * 那可不可以数组＋哈希呢？
     * 显然是可以的啦
     * 补充！！！！
     * 链表的特点就是查找元素慢（因为链表不是连续存储的，查找元素需要遍历（是通过一个一个的指针链接起来的）整个数组）
     * 但是新增和删除元素很快
     */
    List<Integer> nums;
    Map<Integer, Integer> map;
    Random random;

    //初始化
    public SuanFa380() {
        nums = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();

    }

    public boolean insert(int val) {
        //如果map中存在val为键的数则返回为fasle
        if (map.containsKey(val)) {
            return false;
        }
        //因为是可变数组，所以每一次新增都是一次扩展数组的行为
        //例如最初是【】，size是0，做一遍后，下一次是【0】.size则是1，后续将size作为值存在hash中
        int size = nums.size();
        nums.add(val);
        return true;


    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }

      return true;
    }
}
